// Copyright 2011 Google Inc. All Rights Reserved.
// Author: jacobsa@google.com (Aaron Jacobs)
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

var DirectedAcyclicGraph = flame.internal.DirectedAcyclicGraph;
var GraphEdge = flame.internal.GraphEdge;

//////////////////////////////////////////////////////
// Helpers
//////////////////////////////////////////////////////

function hasElementsOrdered(elem1, elem2) {
  var baseDescription =
      gjstest.stringify(elem1) + ' before ' + gjstest.stringify(elem2);

  return new gjstest.Matcher(
      'has ' + baseDescription,
      'does not have ' + baseDescription,
      function(candidate) {
        var loc1 = -1;
        var loc2 = -1;

        for (var i = 0; i < candidate.length; ++i) {
          if (loc1 == -1 && candidate[i] == elem1) loc1 = i;
          if (loc2 == -1 && candidate[i] == elem2) loc2 = i;
        }

        if (loc1 != -1 && loc2 != -1 && loc1 < loc2) {
          return true;
        }

        return false;
      });
}

function whenSorted(matcher) {
  return new gjstest.Matcher(
      'when sorted, ' + matcher.description,
      'when sorted, ' + matcher.negativeDescription,
      function(candidate) {
        var sortedCandidate = [];
        for (var i = 0; i < candidate.length; ++i) {
          sortedCandidate.push(candidate[i]);
        }

        sortedCandidate.sort();
        return matcher.predicate(sortedCandidate);
      });
}

function makeNodesFromEdges(edges) {
  var nodes = new flame.internal.StringSet;
  for (var i = 0; i < edges.length; ++i) {
    nodes.insert(edges[i].fromNode);
    nodes.insert(edges[i].toNode);
  }

  return nodes;
}

//////////////////////////////////////////////////////
// Constructor
//////////////////////////////////////////////////////

function ConstructorTest() {}
registerTestSuite(ConstructorTest);

ConstructorTest.prototype.CycleInGraph = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('burrito', 'taco'),
      new GraphEdge('taco', 'tostada'),
      new GraphEdge('tostada', 'burrito'),
  ];

  var nodes = makeNodesFromEdges(edges);

  expectThat(function() { new DirectedAcyclicGraph(nodes, edges) },
             throwsError(/Cycle.*in.*graph.*(burrito|taco|tostada)/));
};

ConstructorTest.prototype.UnknownFromNodeInEdge = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('burrito', 'taco'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);
  nodes.remove('burrito');

  expectThat(function() { new DirectedAcyclicGraph(nodes, edges) },
             throwsError(/Unknown.*node.*burrito/));
};

ConstructorTest.prototype.UnknownToNodeInEdge = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('burrito', 'taco'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);
  nodes.remove('taco');

  expectThat(function() { new DirectedAcyclicGraph(nodes, edges) },
             throwsError(/Unknown.*node.*taco/));
};

//////////////////////////////////////////////////////
// sortTopologically
//////////////////////////////////////////////////////

function TopologicalSortTest() {}
registerTestSuite(TopologicalSortTest);

TopologicalSortTest.prototype.UnknownNodeInList = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['foo', 'taco', 'bar'];
  expectThat(function() { graph.sortTopologically(sorted) },
             throwsError(/Unknown.*node.*taco/));
};

TopologicalSortTest.prototype.NoEdgesEmptyList = function() {
  var edges = [
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = [];
  graph.sortTopologically(sorted);

  expectThat(sorted, elementsAre([]));
};

TopologicalSortTest.prototype.SomeEdgesEmptyList = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = [];
  graph.sortTopologically(sorted);

  expectThat(sorted, elementsAre([]));
};

TopologicalSortTest.prototype.NoEdgesNonEmptyList = function() {
  var edges = [
  ];

  var nodes = makeNodesFromEdges(edges);
  nodes.insert('foo');
  nodes.insert('bar');

  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['foo', 'bar'];
  graph.sortTopologically(sorted);

  expectEq(2, sorted.length);
  expectThat(sorted, contains('foo'));
  expectThat(sorted, contains('bar'));
};

TopologicalSortTest.prototype.DisconnectedNodes = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('baz', 'qux'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['bar', 'baz'];
  graph.sortTopologically(sorted);

  expectEq(2, sorted.length);
  expectThat(sorted, contains('bar'));
  expectThat(sorted, contains('baz'));
};

TopologicalSortTest.prototype.OneNodeOnlyIncomingEdges = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['baz'];
  graph.sortTopologically(sorted);

  expectEq(1, sorted.length);
  expectThat(sorted, contains('baz'));
};

TopologicalSortTest.prototype.ThreeNodesOnlyIncomingEdges = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
      new GraphEdge('foo', 'taco'),
      new GraphEdge('burrito', 'tostada'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['taco', 'tostada', 'baz'];
  graph.sortTopologically(sorted);

  expectEq(3, sorted.length);
  expectThat(sorted, contains('taco'));
  expectThat(sorted, contains('tostada'));
  expectThat(sorted, contains('baz'));
};

TopologicalSortTest.prototype.OneEdgeInSubgraph = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['baz', 'bar'];
  graph.sortTopologically(sorted);

  expectEq(2, sorted.length);
  expectThat(sorted, contains('bar'));
  expectThat(sorted, contains('baz'));

  expectThat(sorted, hasElementsOrdered('baz', 'bar'));
};

TopologicalSortTest.prototype.SubgraphIsATree = function() {
  var edges = [
      new GraphEdge('bar', 'baz'),
      new GraphEdge('foo', 'bar'),
      new GraphEdge('taco', 'burrito'),
      new GraphEdge('bar', 'taco'),
      new GraphEdge('taco', 'tostada'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['baz', 'burrito', 'taco', 'bar'];
  graph.sortTopologically(sorted);

  expectEq(4, sorted.length);
  expectThat(sorted, contains('bar'));
  expectThat(sorted, contains('baz'));
  expectThat(sorted, contains('taco'));
  expectThat(sorted, contains('burrito'));

  expectThat(sorted, hasElementsOrdered('baz', 'bar'));
  expectThat(sorted, hasElementsOrdered('burrito', 'taco'));
  expectThat(sorted, hasElementsOrdered('taco', 'bar'));
};

TopologicalSortTest.prototype.SubgraphIsNotATree = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['bar', 'baz', 'foo'];
  graph.sortTopologically(sorted);

  expectEq(3, sorted.length);
  expectThat(sorted, contains('foo'));
  expectThat(sorted, contains('bar'));
  expectThat(sorted, contains('baz'));

  expectThat(sorted, hasElementsOrdered('bar', 'foo'));
  expectThat(sorted, hasElementsOrdered('baz', 'bar'));
  expectThat(sorted, hasElementsOrdered('baz', 'foo'));
};

TopologicalSortTest.prototype.TwoComponentsInGraph = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),

      new GraphEdge('taco', 'burrito'),
      new GraphEdge('burrito', 'tostada'),
      new GraphEdge('taco', 'tostada'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['baz', 'bar', 'burrito', 'taco', 'tostada'];
  graph.sortTopologically(sorted);

  expectEq(5, sorted.length);
  expectThat(sorted, contains('bar'));
  expectThat(sorted, contains('baz'));
  expectThat(sorted, contains('taco'));
  expectThat(sorted, contains('burrito'));
  expectThat(sorted, contains('tostada'));

  expectThat(sorted, hasElementsOrdered('baz', 'bar'));
  expectThat(sorted, hasElementsOrdered('burrito', 'taco'));
  expectThat(sorted, hasElementsOrdered('tostada', 'burrito'));
  expectThat(sorted, hasElementsOrdered('tostada', 'taco'));
};

TopologicalSortTest.prototype.IntermediatePathNotInSet = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);

  var sorted = ['baz', 'foo'];
  graph.sortTopologically(sorted);

  expectEq(2, sorted.length);
  expectThat(sorted, contains('foo'));
  expectThat(sorted, contains('baz'));

  expectThat(sorted, hasElementsOrdered('baz', 'foo'));
};

//////////////////////////////////////////////////////
// addReachableNodes
//////////////////////////////////////////////////////

function AddReachableNodesTest() {}
registerTestSuite(AddReachableNodesTest);

AddReachableNodesTest.prototype.UnknownNode = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
  ];

  var nodes = makeNodesFromEdges(edges);
  var graph = new DirectedAcyclicGraph(nodes, edges);
  var result = new flame.internal.StringSet;

  expectThat(function() { graph.addReachableNodes('qux', result) },
             throwsError(/Unknown.*node.*qux/));
};

AddReachableNodesTest.prototype.NoEdges = function() {
  var edges = [
  ];

  var nodes = new flame.internal.StringSet;
  nodes.insert('foo');
  nodes.insert('bar');

  var graph = new DirectedAcyclicGraph(nodes, edges);
  var result = new flame.internal.StringSet;
  graph.addReachableNodes('foo', result);

  expectThat(result.getElements(), whenSorted(elementsAre(['foo'])));
};

AddReachableNodesTest.prototype.DisconnectedNode = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);
  nodes.insert('taco');

  var graph = new DirectedAcyclicGraph(nodes, edges);
  var result = new flame.internal.StringSet;
  graph.addReachableNodes('taco', result);

  expectThat(result.getElements(), whenSorted(elementsAre(['taco'])));
};

AddReachableNodesTest.prototype.OnlyIncomingEdges = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);

  var graph = new DirectedAcyclicGraph(nodes, edges);
  var result = new flame.internal.StringSet;
  graph.addReachableNodes('baz', result);

  expectThat(result.getElements(), whenSorted(elementsAre(['baz'])));
};

AddReachableNodesTest.prototype.OneOutgoingEdge = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);

  var graph = new DirectedAcyclicGraph(nodes, edges);
  var result = new flame.internal.StringSet;
  graph.addReachableNodes('bar', result);

  expectThat(result.getElements(), whenSorted(elementsAre(['bar', 'baz'])));
};

AddReachableNodesTest.prototype.GraphIsATree = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
        new GraphEdge('baz', 'taco'),
        new GraphEdge('baz', 'burrito'),
          new GraphEdge('burrito', 'tostada'),
  ];

  var nodes = makeNodesFromEdges(edges);

  var graph = new DirectedAcyclicGraph(nodes, edges);
  var result;

  result = new flame.internal.StringSet;
  graph.addReachableNodes('baz', result);
  expectThat(result.getElements(),
             whenSorted(
                 elementsAre([
                     'baz',
                     'burrito',
                     'taco',
                     'tostada',
  ])));

  result = new flame.internal.StringSet;
  graph.addReachableNodes('foo', result);
  expectThat(result.getElements(),
             whenSorted(
                 elementsAre([
                     'bar',
                     'baz',
                     'burrito',
                     'foo',
                     'taco',
                     'tostada',
  ])));
};

AddReachableNodesTest.prototype.SubgraphIsNotATree = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),
  ];

  var nodes = makeNodesFromEdges(edges);

  var graph = new DirectedAcyclicGraph(nodes, edges);
  var result = new flame.internal.StringSet;
  graph.addReachableNodes('foo', result);

  expectThat(result.getElements(),
             whenSorted(
                 elementsAre([
                     'bar',
                     'baz',
                     'foo',
  ])));
};

AddReachableNodesTest.prototype.DoesntClearInput = function() {
  var edges = [
      new GraphEdge('foo', 'bar'),
      new GraphEdge('foo', 'baz'),
      new GraphEdge('bar', 'baz'),

      new GraphEdge('foo', 'a'),
      new GraphEdge('a', 'b'),
  ];

  var nodes = makeNodesFromEdges(edges);

  var graph = new DirectedAcyclicGraph(nodes, edges);

  var result = new flame.internal.StringSet;
  result.insert('a');
  result.insert('b');

  graph.addReachableNodes('foo', result);

  expectThat(result.getElements(),
             whenSorted(
                 elementsAre([
                     'a',
                     'b',
                     'bar',
                     'baz',
                     'foo',
  ])));
};
